全国2010年1月高等教育自学考试
数据结构导论试题
课程代码：02142

一、单项选择题(本大题共15小题，每小题2分，共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1.下述文件中适合于磁带存储的是（ ）
A.顺序文件
B.索引文件
C.散列文件
D.多关键字文件

2.某二叉树的后根遍历序列为dabec，中根遍历序列为debac，则先根遍历序列为（ ）
A.acbed
B.becab
C.deabc
D.cedba

3.含有n个结点的二叉树用二叉链表表示时，空指针域个数为( )
A.n-1
B.n
C.n+1
D.n+2

4.在一个图中，所有顶点的度数之和与图的边数的比是( )
A.1∶2
B.1∶1
C.2∶1
D.4∶1

5.长度为n的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为( )
A.O(1)
B.O(1og₂n)
C.O(n)
D.O(n²)

6.下述几种排序方法中，要求内存量最大的是( )
A.插入排序
B.快速排序
C.归并排序
D.选择排序

7.对n个不同值进行冒泡排序，在元素无序的情况下比较的次数为( )
A.n-1
B.n
C.n+1
D.n(n-1)／2

8.对线性表进行二分查找时，要求线性表必须( )
A.以顺序方式存储
B.以链式方式存储
C.以顺序方式存储，且结点按关键字有序排列
D.以链接方式存储，且结点按关键字有序排列

9.在表长为n的顺序表上做删除运算，其平均时间复杂度为( )
A.O(1)
B.O(n)
C.O(nlog₂n)
D.O(n²)

10.当利用大小为n的数组顺序存储一个队列时，该队列的最大容量为( )
A.n-2
B.n-1
C.n
D.n+1

11.有关插入排序的叙述，错误的是( )
A.插入排序在最坏情况下需要O(n²)时间
B.插入排序在最佳情况可在O(n)时间内完成
C.插入排序平均需要O(nlog₂n)时间
D.插入排序的空间复杂度为O(1)

12.有关树的叙述正确的是( )
A.每一个内部结点至少有一个兄弟
B.每一个叶结点均有父结点
C.有的树没有子树
D.每个树至少有一个根结点与一个叶结点。

13.循环队列存储在数组元素A[0]至A[m]中，则入队时的操作为( )
A.rear=rear+1
B.rear=(rear+1)％(m-1)
C.rear=(rear+1)％m
D.rear=(rear+1)％(m+1)

14.关于串的的叙述，不正确的是( )
A.串是字符的有限序列
B.空串是由空格构成的串
C.替换是串的一种重要运算

D.串既可以采用顺序存储，也可以采用链式存储
15.对称矩阵A[N][N]，A[1][1]为首元素，将下三角(包括对角线)元素以行优先顺序存储到一维数组元素T[1]至T[N(N+1)／2]中，则任一上三角元素A[i][j]存于T[k]中，下标k为( )
A.i(i-1)／2+j
B.j(j-1)／2+i
C.i(j-i)／2+1
D.j(i-1)／2+l